using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0763. 划分字母区间")]
    public class No0763_PartitionLabels : AbsBaseTestItem
    {
        /*
        字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
        */

        public override void OnTest()
        {
            Assert.TestExe(PartitionLabels,
                "ababcbacadefegdehijhklij",
                new List<int>() { 9, 7, 8 });
        }

        public IList<int> PartitionLabels(string S)
        {
            int[] last = new int[26];
            int len = S.Length;
            for (int i = 0; i < len; i++)
            {
                last[S[i] - 'a'] = i;
            }
            List<int> ans = new List<int>();
            int start = 0, end = 0;
            for (int i = 0; i < len; i++)
            {
                end = Math.Max(end, last[S[i] - 'a']);
                if (i == end)
                {
                    ans.Add(end - start + 1);
                    start = end + 1;
                }
            }
            return ans;
        }
    }
}
